from typing import List


class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board:
            return
        w = len(board[0])
        h = len(board)
        def dfs(i,j):
            if 0>i or i >w-1 or j < 0 or j>h-1 or board[i][j] != 'O':
                return
            board[i][j] = 'A'
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)


        for i in range(h):
            dfs(i,0)
            dfs(i,w-1)
        for j in range(w):
            dfs(0,i)
            dfs(h-1,j)

        for i in range(h):
            for j in range(w):
                if board[i][j] == "A":
                    board[i][j] = "O"
                elif board[i][j] == "O":
                    board[i][j] = "X"




if __name__ == '__main__':
    board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
    solution = Solution()
    val = solution.solve(board)
    print(board)